import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class hamiltonDP {
	
	static String[] edges = {"0:1", "0:3", "1:2", "1:4", "2:5", "3:4", "4:5"};

	public static void main(String[] args) {
		Graph g = new Graph();
		for(String e : edges) {
			String[] v = e.split(":");
			g.addEdge(v[0], v[1]);
		}
		
		System.out.println("G besitzt einen Hamiltonkreis: " + g.isHamiltonian());
	}
	
}

class Graph {
	
	HashMap<Integer, HashSet<Integer>> edges = new HashMap<>();
	int N = 0;
	int M = 0;
	
	void addVertex(int i) {
		if(edges.containsKey(i)) return;
		
		N++;
		edges.put(i, new HashSet<>());
	}
	
	void addVertex(String i) {
		addVertex(Integer.parseInt(i));
	}
	
	void addEdge(int from, int to) {
		addVertex(from);
		addVertex(to);
		
		M++;
		edges.get(from).add(to);
		edges.get(to).add(from);
	}
	
	void addEdge(String from, String to) {
		addEdge(Integer.parseInt(from), Integer.parseInt(to));
	}
	
	boolean hasEdge(int from, int to) {
		return edges.get(from).contains(to);
	}
	
	boolean isHamiltonian() {
		int numSets = (1 << (N-1))-1;
		
		boolean P[][] = new boolean[numSets+1][N];
		
		// Initialisierung
		for(int i = 1; i < N; i++) {
			if(hasEdge(0, i)) P[1 << (i-1)][i] = true;
		}
		
		ArrayList<LinkedList<Integer>> subgraphs = new ArrayList<>();
		for(int i = 0; i < N+1; i++) subgraphs.add(new LinkedList<>());
		for(int i = 0; i < numSets+1; i++) {
			subgraphs.get(Integer.bitCount(i)+1).add(i);
		}
		
		// Iteration
		for(int s = 3; s < N+1; s++) {
			for(int S : subgraphs.get(s)) {
				for(int x = 1; x < N; x++) {
					if(!inSet(S, x)) continue;
					for(int y = 1; y < N; y++) {
						if(x == y) continue;
						P[S][x] = P[S][x] || (P[setMinus(S, x)][y] && hasEdge(x, y) && inSet(S, y));
					}
				}
			}
		}
		
//		for(int i = 0; i < numSets+1; i++) {
//			System.out.print(Integer.toString(i, 2) + ":\t");
//			for(int o = N-1; o >= 0; o--) {
//				System.out.print(P[i][o] ? 1 : 0);
//			}
//			System.out.println();
//		}
		
		boolean out = false;
		for(int x = 1; x < N; x++) {
			out = out || (P[numSets][x] && hasEdge(0,x)); 
		}
		return out;
	}
	
	private boolean inSet(int S, int i) {
		return (S & (1 << (i-1))) != 0;
	}
	
	private int setMinus(int S, int i) {
		return S & ~(1 << (i-1));
	}
	
}